package cn.camel.algorithm.tree.trie;
import java.util.ArrayList;
import java.util.List;

/**
 * @author: Camel
 * @description: Trie实现
 * @date: 2025/10/14 20:02
 */
public class Trie {
    private TrieNode root;
    /**
     * 构造函数，初始化Trie树
     * 创建一个空的根节点
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * 插入单词到Trie树中
     * @param word 要插入的单词
     */
    public void insert(String word) {
        if(word == null || word.length() == 0) return;
        TrieNode node = root;
        // 遍历单词字母
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.containKey(c)){
                node.putChar(c);
            }
            node = node.getChild(c);
        }
        node.setIsWord(true); // 设置为单词结尾
    }

    /**
     * 在Trie树中搜索指定单词
     * @param word 要搜索的单词
     * @return 如果单词存在返回true，否则返回false
     */
    public boolean searchWord(String word) {
        if(word == null || word.length() == 0) return false;
        TrieNode node = searchPrefix(word);
        return node != null && node.isWordOrNot();
    }

    /**
     * 检查Trie树中是否存在指定前缀
     * @param prefix 要检查的前缀
     * @return 如果前缀存在返回true，否则返回false
     */
    public boolean startsWith(String prefix) {
        if(prefix == null || prefix.length() == 0) return false;
        return searchPrefix(prefix) != null;
    }

    /**
     * 查找前缀对应的节点
     * @param prefix 要查找的前缀
     * @return 如果前缀存在，返回前缀最后一个字符对应的节点；否则返回null
     */
    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (!node.containKey(c)){
                return null;
            }
            node = node.getChild(c);
        }
        return node;
    }

    /**
     * 搜索所有以指定前缀开头的单词
     * @param prefix 搜索的前缀
     * @return 所有匹配的单词列表
     */
    public List<String> searchWordsWithPrefix(String prefix){
        if(prefix == null || prefix.length() == 0) return new ArrayList<>();
        List<String> result = new ArrayList<>();
        TrieNode node = searchPrefix(prefix);
        if(node != null){
            collectWordsStartWithPrefix(node, result, new StringBuilder(prefix));
        }
        return result;
    }

    /**
     * 递归收集以指定节点开始的所有单词
     * @param node 当前节点
     * @param result 结果列表，用于存储找到的单词
     * @param strbuilder 当前构建的字符串
     */
    private void collectWordsStartWithPrefix(TrieNode node, List<String> result, StringBuilder strbuilder) {
        if(node.isWordOrNot()){
            result.add(strbuilder.toString());
        }
        for(int i = 0;i < 26;i ++){
            char c = (char)('a' + i);
            if(node.containKey(c)){
                strbuilder.append(c);
                collectWordsStartWithPrefix(node.getChild(c), result, strbuilder);
                strbuilder.deleteCharAt(strbuilder.length() - 1); // 回溯
            }
        }
    }


    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.insert("application");
        trie.insert("blue");
        trie.insert("blueface");
        trie.insert("blwww");
        System.out.println(trie.searchWord("blue"));
        System.out.println(trie.searchWordsWithPrefix("app"));
        System.out.println(trie.searchWordsWithPrefix("bl"));
    }
}
